package com.leetcode.array;

/**
 * Given an array with n objects colored red, white 
 * or blue, sort them so that objects of the same color 
 * are adjacent, with the colors in the order red, 
 * white and blue.
 * 
 * Here, we will use the integers 0, 1, and 2 to 
 * represent the color red, white, and blue respectively.
 * 
 * *Note:
 * You are not suppose to use the library's sort 
 * function for this problem.
 */
import java.util.Arrays;

public class SortColors {

	public static void main(String[] args) {
		int[] nums={1,0,0,2,2,1,1,1,2,2,0};
		int[] nums1={1,2,1};
		int[] nums2={1,2,2,2,2,0,0,0,1,1};
        sortColors(nums2);
	}

	public static void sortColors(int[] nums) {
		int left=0,right=nums.length-1;
		for(int i=left,j=right;i<=right/2&&i<=j;){
			while(nums[i]<nums[j]){
				if(nums[i]<=nums[i+1])
				i++;
				else{
					int temp=nums[i];nums[i]=nums[i+1];nums[i+1]=temp;
					i=left;
				}
			}
		   while(nums[i]>nums[j]){
			   int temp=nums[i];nums[i]=nums[j];nums[j]=temp;
			   if(nums[i]<=nums[i+1])
			   i++;
			   break;
		   }
		   while(nums[i]==nums[j]){
			   if(j==0) break;
			   if(nums[j]>=nums[j-1])
			   j--;
			   else{
				   int temp=nums[j];nums[j]=nums[j-1];nums[j-1]=temp;
				   j=right;
			   }
		   }
		   if(j==0) break;
		}
		for(int i=0;i<nums.length;i++){
			System.out.print(nums[i]+" ");
		}
	}
	public static void sortColors1(int[] nums) {
		Arrays.sort(nums);
		for(int i=0;i<nums.length;i++){
			System.out.print(nums[i]+" ");
		}
	}
}
